/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 26
 * Time: 13:42
 */
//牛客 旋转数组的最小数字
public class Solution1 {
    public int minNumberInRotateArray(int[] array) {
       int left = 0;
       int right = array.length - 1;
       while(left < right) {
           int mid = (left + right) / 2;//因为mid有可能和left重合，从而right--错过最小值，比如数组为4、3，所以用array[right]与array[mid]做对比而不用array[left]
           if(array[mid] < array[right]) {//array[mid]<array[right]说明array[mid]在右边递增的子序列中，已经进入了含有最小值的目标序列，则right=mid
               right = mid;
           } else if (array[mid] > array[right]) {//array[mid]>array[right]说明array[mid]在左边递增的子序列中，没有进入了含有最小值的目标序列，则left=mid+1
               left = mid + 1;
           }else {//array[mid]=array[right]，无法确定array[mid]是在右边递增的子序列还是在左边递增的子序列，只能right--缩小判断范围
               right--;//用left++会有问题
           }
       }
       return array[left];
    }
}
